package com.tgy.sequence;

import org.springframework.util.StringUtils;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2020-11-23 09:24
 */
public class KMP {

    public static int indexOf(String text,String pattern) {

        if (StringUtils.isEmpty(text) || StringUtils.isEmpty(pattern) || text.length() < pattern.length()) {

            return -1;
        }

        int[] nexts = nexts(pattern);

        System.out.println(Arrays.toString(nexts));

        int ti = 0,pi = 0;

        int lastIndex = text.length() - pattern.length();

        while (pi < pattern.length()) {

            /**
             * 每次pi回到第一个位置时，如果小于0，则 ti向前加1，pi右-1变成0，然后下一轮循环从 ti的下一位置和pi为0开始比较，正好从头开始
             */
            if (text.charAt(ti) == pattern.charAt(pi)) {

                ti++;
                pi++;
            }else {

                if (ti > lastIndex) {
                    return  -1;
                }

                pi = nexts[pi];
                if (pi <= 0) {

                    ti++;
                    pi = 0;
                }
            }
        }

        return ti - pi;
    }

    /**
     * next 求 pattern 每一个位置的真前缀与真后缀的最长公共子串
     * @param pattern
     * @return
     */
    private static int[] nexts(String pattern) {

        int[] nexts = new int[pattern.length()];

        nexts[0] = -1;
        int index = 2;

        while (index < pattern.length()) {

            int i = index - 1;
            while (true) {

                if (pattern.charAt(index - 1) == pattern.charAt(nexts[i]) &&
                        pattern.charAt(index) != pattern.charAt(nexts[i] + 1)) {

                    nexts[index++] = nexts[i] + 1;
                    break;
                }else {

                    i = nexts[i];
                    if (i <= 1) {

                        nexts[index++] = 0;
                        break;
                    }
                }
            }
        }

        return nexts;
    }
}
